In a packet data communications system, for example the internet or a radio packet service (e.g. GPRS, General Packet Radio Service), packets may be lost between the sending node in the system and the receiving node in the system. According to the quality of the channel, a differing proportion of the packets may be lost, such proportion varying over time according to various factors. In order for the data to be transmitted successfully, the lost packets will need to be recovered in some way by the receiving node. This is often achieved by the receiving node acknowledging the packets received such that the sending node can determine which packets have been received and selectively retransmit the lost packets. A system which requires little retransmission of packets is more efficient than a network which requires considerable retransmission of packets.
Multicast data distribution over packet networks has been proposed and this means that the sending node in the network is now sending the same data to many receiving nodes. There may in some circumstances be hundreds or thousands of receiving nodes, for example in a packet network sending football scores to the mobile phones belonging to all those located in a football stadium. When sending to many receiving nodes, the loss properties of the link (or channel) between the sending node and each receiving node will vary significantly. The actual data which is lost will also vary between receivers (i.e. if all receiving nodes receive 8 out of 10 packets sent, each node will not receive the same 8 packets). In such a network it is not practical for each received packet to be acknowledged by each of the receiving nodes as this would create a huge overhead in signalling. Instead forward error correction (FEC) techniques are used to ensure that each receiving node has a high probability of recovering the original data from the packets received, even though each receiving node may have received different parts of the encoded data stream.
A number of FEC schemes are known and in order for a receiving node to be able to extract the data from the received signal, the receiving node must know the FEC scheme which is being used. The step of extraction of the data from the received information which is FEC coded (i.e. the decoding step) requires a lot of processing. In order that this decoding can be done in a realistic time, it is usual to develop specialised decoding software for the particular scheme to be employed.
One class of forwards error correction techniques that is known is Low Density Parity Check techniques.